package com.mccken.practice.top100.Top_1$20.top_11;

/**
 * @program: mccken-collect
 * @description:
 * @author: mccken
 * @create: 2024-01-02 14:44
 **/
public class MaxSubArray {

	/*
		动态规划
		五部曲：
		1. 定义dp数组
		2. 递推公式
		3. 初始化
		4. 遍历顺序
		5. 打印数组 
				
	 */
	public int maxSubArray(int[] nums) {
		int len = nums.length;
		if (len == 1) {
			return nums[0];
		}

		// dp[i] 定义： 以i结尾的元素，其最大子数组和为 dp[i]
		int[] dp = new int[len];
		// dp[i] = max(dp[i-1]+nums[i], nums[i])
		dp[0] = nums[0];
		int max = dp[0];
		for (int i = 1; i < len; i++) {
			dp[i] = Math.max(dp[i-1]+nums[i], nums[i]);
			if (max < dp[i]) {
				max = dp[i];
			}
		}

//		for (int i = 0; i < dp.length; i++) {
//			System.out.print(dp[i]);
//			System.out.print(" ");
//		}
//		System.out.println();
		return max;
	}
	
	/*
		贪心算法
		从dp[i] = Max(dp[i-1]+nums[i], nums[i]) 可以发现，sums[i]<0就舍弃从头计算了
	 */
	
	public int maxSubArray1(int[] nums) {
		int len = nums.length;
		if (len == 1) {
			return nums[0];
		}

		int max = Integer.MIN_VALUE;
		int sum = 0;
		for (int i = 0; i < len; i++) {
			sum += nums[i];
			max = Math.max(max, sum);
			if (sum < 0) {
				sum = 0;
			}
		}

		return max;
	}

	public static void main(String[] args) {
		MaxSubArray maxSubArray = new MaxSubArray();
//		System.out.println(maxSubArray.maxSubArray(new int[]{-2, 1, -3, 4, -1, 2, 1, -5, 4}));
//		System.out.println(maxSubArray.maxSubArray(new int[]{5, 4, -1, 7, 8}));
//		System.out.println(maxSubArray.maxSubArray(new int[]{-1}));
		System.out.println(maxSubArray.maxSubArray(new int[]{-1, -2}));
	}

}
